  IOI. 17 (Sectoare de cerc). Se considera un cerc mpartit n sectoare. Se dau la intrare
numerele k(k20),n(n6),m(m20); n reprezinta numarul de sectoare. In fiecare sector se
depune un numar ntreg mai mare sau egal cu k. Aceste numere trebuiesc alese n asa fel nct sa se
poata obtine o secventa ct mai mare de numere ntregi consecutive ncepnd cu m, construita astfel:
fiecare numar este identic cu un numar dintr-un sector sau este suma numerelor din doua sau mai
multe sectoare consecutive (luate o singura data). Iesirea trebuie sa contina:
- lungimea celei mai lungi secvente de numere care poate fi generata conform regulii de mai sus;
- toate combinatiile posibile de numere de pe cerc care pot produce aceasta secventa (cte una pe
linie). Fiecare astfel de combinatie este o lista de numere ncepnd cu cel mai mic (care nu este
neaparat unic).
Exemplu: pentru intrarea
1
2
5
iesirea va fi
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4
===================================================
Algoritm:
              Din fiierul de intrare se citesc n ordine n (num[rul de sectoare), mm (cel mai mic num[r ce
trebuie realizat) i k (valoarea minim[ a numerelor ce pot fi nscrise n sectoare).
               Construiesc lista sm avnd nsm=n(n-1)+1 elemente. Pentru fiecare i=1,...,n-1, valoarea
i i succesiunea de i sectoare ce ncepe de pe poziia kk vor fi plasate n list[ pe poziia(i-1)n+kk.
Pe poziia nsm va fi plasat n i succesiunea 1,2,...,n de sectoare consecutive.
               Este evident c[ pentru o etichetare dat[ a sectoarelor, parcurgerea listei sm va permite
determinarea tuturor numerelor realizabile. Cerinele problemei constau ns[ n a determina o
etichetare optim[ a sectoarelor.
               O etichetare a sectoarelor va fi un vector cu n componente (tipul tvec). Soluia problemei va
fi un vector solv de descrieri ale etichet[rilor.
               Prin ms este notat[ valoarea maxim[ pentru care exist[ o etichetare astfel nct numerele
mm,mm+1,...,ms s[ fie realizabile. Vom pleca cu ms=0, valoare care nu se va modifica dac[ nu
exist[ soluii (cazul mm<k).
               Orice etichetare vec a sectoarelor va avea cea mai mic[ valoare pe poziia 1. Pentru fiecare
vector vec=(kmin,0,...,0), unde kmin=k,k+1,...,1+mm div 2 se apeleaz[ procedura
bactracking recursiv[ bk prin bk(mm).
               Procedura bk avnd parametrul m urm[rete s[ completeze unele dintre poziiile libere ale lui
vec astfel nct valoarea m s[ fie realizabil[. Consider[m pe rnd elementele listei sm. Se verific[
nti dac[ valoarea m este deja realizabil[ pe baza succesiunii de sectoare ce constituie elementul
curent al listei. In caz afirmativ se apelaz[ bk(m+1), ncercndu-se de a-l face i pe m+1 realizabil.
In caz contrar: dac[ mai exist[ sectoare neetichetate i dac[ exist[ un element din lista sm (o
succesiune de sectoare) astfel nct prin completarea cu valoarea minim[ kmin a sectoarelor libere ale
succesiunii considerate se obine o sum[ ce nu dep[ete m, atunci este apelat[ procedura b, care
ncearc[ s[ completeze sectoarele libere din succesiune astfel nct m s[ devin[ realizabil (dac[
procedura b va reui n aceast[ ncercare, ea va efectua apelul bk(m+1)0, prin care se caut[ a-l face
i pe m+1 realizabil).
             Dac[ procedura bk ajunge s[ fie apelat[ pentru o valoare m cu m-1ms, atunci:
   - dac[ m-1>ms, atunci optimul a fost mbun[t[it i atunci vechiul coninut al lui sol este anulat
i este apelat[ procedura adauga;
   - dac[ m-1=ms, atunci optimul mai poate fi atins nc[ ntr-un mod i este apelat[ procedura
adauga.
               Procedura adauga pleac[ de la un vector soluie, compleaeaz[ poziiile sale neocupate cu
mm i dac[ vectorul astfel obinut nu se afl[ n solv l adaug[ lui solv.
Program:
?????????????????????
--------------------------------------------
